package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 3040. 相同分数的最大操作数目 II
 * @Author: cookLee
 * @Date: 2024-06-08
 */
public class MaxOperationsII {

    /**
     * 主
     * \
     * 输入：nums = [3,2,1,2,3,4]
     * 输出：3
     * 解释：我们执行以下操作：
     * - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
     * - 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
     * - 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
     * 由于 nums 为空，我们无法继续进行任何操作。
     * \
     * 输入：nums = [3,2,6,1,4]
     * 输出：2
     * 解释：我们执行以下操作：
     * - 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
     * - 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
     * 至多进行 2 次操作。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaxOperationsII maxOperations = new MaxOperationsII();
        int[] nums = new int[]{3,2,1,2,3,4};
        System.out.println(maxOperations.maxOperations(nums));
    }

    int[][] memo;
    int[] nums;
    /**
     * 最大操作数：记忆化搜索
     *
     * @param nums nums
     * @return int
     */
    public int maxOperations(int[] nums) {
        int len = nums.length;
        this.nums = nums;
        this.memo = new int[len][len];
        int ans = 0;
        ans = Math.max(ans, this.helper(0, len - 1, nums[0] + nums[len - 1]));
        ans = Math.max(ans, this.helper(0, len - 1, nums[0] + nums[1]));
        ans = Math.max(ans, this.helper(0, len - 1, nums[len - 2] + nums[len - 1]));
        return ans;
    }

    /**
     * 帮手
     *
     * @param i      我
     * @param j      j
     * @param target 目标
     * @return int
     */
    private int helper(int i, int j, int target) {
        for (int k = 0; k < nums.length; k++) {
            Arrays.fill(memo[k], -1);
        }
        return this.dfs(i, j, target);
    }

    /**
     * dfs
     *
     * @param i      我
     * @param j      j
     * @param target 目标
     * @return int
     */
    private int dfs(int i, int j, int target) {
        if (i >= j) {
            return 0;
        }
        if (this.memo[i][j] != -1) {
            return this.memo[i][j];
        }
        int ans = 0;
        if (this.nums[i] + this.nums[i + 1] == target) {
            ans = Math.max(ans, this.dfs(i + 2, j, target) + 1);
        }
        if (this.nums[j - 1] + this.nums[j] == target) {
            ans = Math.max(ans, this.dfs(i, j - 2, target) + 1);
        }
        if (this.nums[i] + this.nums[j] == target) {
            ans = Math.max(ans, this.dfs(i + 1, j - 1, target) + 1);
        }
        this.memo[i][j] = ans;
        return ans;
    }


}
